package leetcode.editor.cn;//给你一个链表数组，每个链表都已经按升序排列。
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。
//
//
//
// 示例 1：
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
//
//
// 示例 2：
//
// 输入：lists = []
//输出：[]
//
//
// 示例 3：
//
// 输入：lists = [[]]
//输出：[]
//
//
//
//
// 提示：
//
//
// k == lists.length
// 0 <= k <= 10^4
// 0 <= lists[i].length <= 500
// -10^4 <= lists[i][j] <= 10^4
// lists[i] 按 升序 排列
// lists[i].length 的总和不超过 10^4
//
// Related Topics 链表 分治 堆（优先队列） 归并排序
// 👍 1669 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import leetcode.editor.cn.entity.ListNode;

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution23 {


    public static void main(String[] args) {

        ListNode node11 = new ListNode(1);
        ListNode node12 = new ListNode(4);
        ListNode node13 = new ListNode(5);

        ListNode node21 = new ListNode(1);
        ListNode node22 = new ListNode(3);
        ListNode node23 = new ListNode(4);

        ListNode node31 = new ListNode(7);
        ListNode node32 = new ListNode(2);
        ListNode node33 = new ListNode(6);

        node12.next = node13;
        node11.next = node12;

        node22.next = node23;
        node21.next = node22;

        node32.next = node33;
        node31.next = node32;




        ListNode[] lists = new ListNode[3];
        lists[0] = node11;
        lists[1] = node22;
        lists[2] = node33;

    }

    // 并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上
    // 这里我们就要用到 优先级队列（二叉堆）
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists.length == 0){
            return null;
        }
        ListNode dummy = new ListNode(-1),p=dummy;
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length,(a,b)->a.val-b.val);
        // 将 k 个链表的头结点加入最小堆
        for (ListNode list : lists) {
            if (list != null){
                queue.add(list);
            }
        }
        while(!queue.isEmpty()){
            // 获取最小节点，接到结果链表中
            ListNode node = queue.poll();
            p.next = node;
            if (node.next != null){
                queue.add(node.next);
            }
            // p指针不断前进
            p = p.next;

        }


        return dummy.next;
    }




}
//leetcode submit region end(Prohibit modification and deletion)
